# https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/description/
# 902. 最大为 N 的数字组合
# medium, 刘小康 2024.09.20
# 数位DP

class Solution:
    def atMostNGivenDigitSet(self, digits: list[str], n: int) -> int:
        num = str(n)
        dp = [[0, 0] for _ in range(len(num) + 1)]
        dp[0][1] = 1
        for i in range(1, len(num) + 1):
            if i > 1:
                dp[i][0] += len(digits) + dp[i - 1][0] * len(digits)
            for d in digits:
                if d == num[i - 1]:
                    dp[i][1] = dp[i - 1][1]
                elif d < num[i - 1]:
                    dp[i][0] += dp[i - 1][1]
                else:
                    break

        return sum(dp[len(num)])